//
// Created by cheng on 2021/02/21.
//

#include <iostream>
#include <vector>

using namespace std;

// 以arr最后一位为基准的数组分割
int Partition(vector<int>& arr);

int main() {
    vector<int> arr = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
    Partition(arr);
    for (auto i : arr) {
        cout << i << " ";
    }
    cout << endl;
}

int Partition(vector<int> &arr) {
    int i = 0, j = arr.size();
    swap(arr[0], arr[j-1]);
    int pos = 0; // 哨兵坐标
    int posValue = arr[pos];
    while (true) {
        while (arr[++i] < posValue && i < j);
        while (arr[--j] > posValue);
        if(i > j) {
            break;
        }
        swap(arr[i], arr[j]);
    }
    arr[pos] = arr[j];
    arr[j] = posValue;
    return j;
}
